public class prog {
}

class Solution {
    public int distributeCandies(int[] candyType) {
        Arrays.sort(candyType);
        int count=1;
        for(int i=1;i<candyType.length&&count<candyType.length/2;i++){
            if(candyType[i]>candyType[i-1]){
                count++;
            }
        }
        return count;
    }
}










class Solution {
    public int[][] matrixReshape(int[][] mat, int r, int c) {
        int row=mat.length;
        int col=mat[0].length;
        if(row*col!=r*c){
            return mat;
        }
        int[][] ans=new int[r][c];
        for(int i=0;i<r*c;i++){
            ans[i/c][i%c]= mat[i/col][i%col];
        }
        return ans;
    }
}










class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int sum=0;
        for(int i=0;i<nums.length;i+=2){
            sum+=nums[i];
        }
        return sum;
    }
}













class Solution {
    public boolean checkRecord(String s) {
        int a=0;
        int l=0;
        int p=0;
        int max=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='P'){
                p++;
                l=0;
            }else if(s.charAt(i)=='A'){
                a++;
                l=0;
            }else if(s.charAt(i)=='L'){
                l++;
                max=Math.max(l,max);
            }
        }
        if(a<2&&max<3){
            return true;
        }
        return false;
    }
}










class Solution {
    public String reverseStr(String s, int k) {
        char[] str=s.toCharArray();
        int len=s.length();
        for(int i=0;i<len;i+=2*k){
            reverse(str,i,Math.min(i+k,len)-1);
        }
        return new String(str);
    }
    public void reverse(char[] str,int i,int len){
        while(i<len){
            char tmp=str[i];
            str[i]=str[len];
            str[len]=tmp;
            len--;
            i++;
        }
    }
}












class Solution {
    public boolean detectCapitalUse(String word) {
        if(word.length()==1){
            return true;
        }
        boolean bool=testing(word.charAt(1));
        for(int i=2;i<word.length();i++){
            if(testing(word.charAt(i))!=bool){
                return false;
            }
        }
        return bool?testing(word.charAt(0)):true;
    }
    public boolean testing(char ch){
        return 'A'<=ch&&ch<='Z';
    }
}











class Solution {
    public boolean checkPerfectNumber(int num) {
        if(num==1){
            return false;
        }
        int sum=1;
        for(int i=2;i*i<num;i++){
            if(num%i==0){
                sum+=i;
                if(i*i!=num){
                    sum+=num/i;
                }
            }
        }
        return sum==num;
    }
}












class Solution {
    public String[] findRelativeRanks(int[] score) {
        int len=score.length;
        int[] arr=new int[len];
        String[] str=new String[len];
        System.arraycopy(score,0,arr,0,len);
        Arrays.sort(arr);
        for(int i=0;i<len;i++){
            int val=len-Arrays.binarySearch(arr,score[i]);
            if(val==1){
                str[i]="Gold Medal";
            }else if(val==2){
                str[i]="Silver Medal";
            }else if(val==3){
                str[i]="Bronze Medal";
            }else {
                str[i]=String.valueOf(val);
            }
        }
        return str;
    }
}
















class Solution {
    public String convertToBase7(int num) {
        StringBuilder str=new StringBuilder();
        int val=0;
        if(num==0){
            str.append(0);
        }
        if(num>0){
            while(num!=0){
                val=num%7;
                str.append(val);
                num/=7;
            }
        }
        if(num<0){
            num=-num;
            while(num!=0){
                val=num%7;
                str.append(val);
                num/=7;
            }
            str.append('-');
        }
        return str.reverse().toString();
    }
}











class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int len1=nums1.length;
        int len2=nums2.length;
        int[] num=new int[len1];
        if(len1==0){
            return num;
        }
        for(int i=0;i<len1;i++){
            int val=nums1[i];
            int j=0;
            while(j<len2&&nums2[j]!=val){
                j++;
            }
            j++;
            while(j<len2&&nums2[j]<val){
                j++;
            }
            if(j==len2){
                num[i]=-1;
                continue;
            }
            num[i]=nums2[j];
        }
        return num;
    }
}








class Solution {
    public int[] constructRectangle(int area) {
        int a=(int)Math.sqrt(area);
        for(;a>=0;a--){
            if(area%a==0){
                break;
            }
        }
        return new int[]{area/a,a};
    }
}











class Solution {
    public String licenseKeyFormatting(String s, int k) {
        StringBuilder str=new StringBuilder();
        for(int i=s.length()-1;i>=0;i--){
            if(s.charAt(i)!='-'){
                str.append(str.length()%(k+1)==k?"-":"").append(s.charAt(i)>91?(char)(s.charAt(i)-32):s.charAt(i));
            }
        }
        return str.reverse().toString();
    }
}









class Solution {
    public boolean repeatedSubstringPattern(String s) {
        return (s+s).indexOf(s,1)!=s.length();
    }
}










class Solution {
    public int arrangeCoins(int n) {
        int fast=0;
        int right=n;
        while(fast<=right){
            long mid=(right-fast)/2+fast;
            Long sum=((mid+1)*mid)/2;
            if(sum==n){
                return (int)mid;
            }else if(sum>n){
                right=(int)mid-1;
            }else{
                fast=(int)mid+1;
            }
        }
        return right;
    }
}










class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> str=new ArrayList<String>();
        for(int i=0;i<12;i++){
            for(int j=0;j<60;j++){
                if(Integer.bitCount(i)+Integer.bitCount(j)==turnedOn){
                    str.add(i+":"+(j<10?"0":"")+j);
                }
            }
        }
        return str;
    }
}












class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length==0){
            return "";
        }
        String str=strs[0];
        for(int i=1;i<strs.length;i++){
            int j=0;
            for(j=0;j<str.length()&&j<strs[i].length();j++){
                if(str.charAt(j)!=strs[i].charAt(j)){
                    break;
                }
            }
            str=str.substring(0,j);
            if(str.equals("")){
                return str;
            }
        }
        return str;
    }
}













class Solution {
    public int numPrimeArrangements(int n) {
        if(n<=2){
            return 1;
        }
        int count=2;
        for(int i=4;i<=n;i++){
            if(isprime(i)){
                count++;
            }
        }
        return (int)(calculate(count)*calculate(n-count)%1000000007);
    }
    public boolean isprime(int i){
        for(int j=2;j<=Math.sqrt(i);j++){
            if(i%j==0){
                return false;
            }
        }
        return true;
    }
    public long calculate(int n){
        long ret=1;
        for(int i=2;i<=n;i++){
            ret*=i;
            ret%=1000000007;
        }
        return ret;
    }
}













class Solution {
    public int[] finalPrices(int[] prices) {
        for(int i=0;i<prices.length-1;i++){
            for(int j=i+1;j<prices.length;j++){
                if(prices[i]>=prices[j]){
                    prices[i]-=prices[j];
                    break;
                }
            }
        }
        return prices;
    }
}











class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        for(int i=0;i<arr.length-1;i++){
            if(arr[i]>arr[i+1]){
                return i;
            }
        }
        return -1;
    }
}









class Solution {
    public int countSquares(int[][] matrix) {
        int row=matrix.length;
        int col=matrix[0].length;
        int[][] dp=new int[row][col];
        int count=0;
        for(int i=0;i<row;i++){
            dp[i][0]=matrix[i][0];
            count+=dp[i][0];
        }
        for(int i=0;i<col;i++){
            dp[0][i]=matrix[0][i];
            count+=dp[0][i];
        }
        if(matrix[0][0]==1){
            count--;
        }
        for(int i=1;i<row;i++)
        {
            for(int j=1;j<col;j++){
                if(matrix[i][j]==1){
                    dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                    count+=dp[i][j];
                }
            }
        }
        return count;
    }
}












class Solution {
    public int[] singleNumber(int[] nums) {
        int sum=0;
        for(int num : nums){
            sum^=num;
        }
        int div=1;
        while((div&sum)==0){
            div<<=1;
        }
        int a=0;
        int b=0;
        for(int num : nums){
            if((div&num)!=0){
                a^=num ;
            }else{
                b^=num;
            }
        }
        return new int[]{a,b};
    }
}












class Solution {
    public int singleNumber(int[] nums) {
        int sum=0;
        int tmp=0;
        for(int i=0;i<32;i++){
            tmp=0;
            for(int num : nums){
                tmp += ((num>>i)&1);
            }
            if(tmp%3!=0){
                sum |= (1<<i);
            }
        }
        return sum;
    }
}